package com.arron.algorithm.leetcodetop100.动态规划.子序列or子数组;

/**
 * 1143. 最长公共子序列
 *  经典题解：
 *  https://leetcode.cn/problems/longest-common-subsequence/solutions/67460/dong-tai-gui-hua-zhi-zui-chang-gong-gong-zi-xu-lie/?envType=study-plan-v2&envId=top-100-liked
 */
public class 最长公共子序列 {

    int[][] dp;

    public int longestCommonSubsequence_dfs(String text1, String text2) {
        dp = new int[text1.length()][text2.length()];
        for (int i = 0; i < text1.length(); i++) {
            for (int j = 0; j < text2.length(); j++) {
                dp[i][j] = -1;
            }
        }
        return longestCommonSubsequence_dfs(text1.toCharArray(),text1.length()-1,text2.toCharArray(),text2.length()-1);
    }

    //自顶向下的 记忆化 递归
    public int longestCommonSubsequence_dfs(char[] chars1,int i,char[] chars2,int j){

        if (i<0 || j<0){
            return 0;
        }
        if (dp[i][j] !=-1){
            return dp[i][j];
        }
        if (chars1[i] == chars2[j]){
            //相等，则序列长度加一，然后继续匹配剩余的 s1[0...i-1]和s2[0...j-1]
            dp[i][j] = longestCommonSubsequence_dfs(chars1,i-1,chars2,j-1)+1;
        }else {
            //不相等，则去取 s1[0...i-1] ，s2[0...j]获得的lcs 和s1[0...i],s2[0...j-1]获得的lcs的最大值
            dp[i][j] = Math.max(longestCommonSubsequence_dfs(chars1,i-1,chars2,j),longestCommonSubsequence_dfs(chars1,i,chars2,j-1));
        }
        return dp[i][j];
    }

    //自底向上的动态规划
    public int longestCommonSubsequence(String text1, String text2) {
        //dp[i][j] 代表字符串s1[0...i] 和 s2[0...j] 的最长公共子序列长度
        int[][] dp = new int[text1.length()+1][text2.length()+1];

        //初始化第一行的每一列都为0，s1,s2前面加一个空串 方便初始化，所以第一行和第一列 最长的公共子序列长度都是 0
        for (int i = 0; i < text2.length(); i++) {
            dp[0][i] = 0;
        }

        for (int i = 0; i < text1.length(); i++) {
            dp[i][0] = 0;
        }
        char[] chars1 = text1.toCharArray();
        char[] chars2 = text2.toCharArray();
        for (int i = 1; i <= text1.length(); i++) {
            for (int j = 1; j <= text2.length() ; j++) {
                if (chars1[i-1] == chars2[j-1]){
                    dp[i][j] = 1+ dp[i-1][j-1];
                }else {
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }

            }

        }
        return dp[text1.length()][text2.length()];

    }




    public static void main(String[] args) {

        最长公共子序列 longestCommonSubsequence = new 最长公共子序列();
        System.out.println(longestCommonSubsequence.longestCommonSubsequence("cey", "ex"));
    }

}
